FIG. 1 shows a computer system 20. The computer system 20 has one or more processors 22 connected to a system bus 24. A main memory 26 and one or more input/output (I/O) bridges 28 are also connected to the system bus 24. An input/output device 30, such as a computer keyboard and display screen, is connected to I/O bridge 28.
The processor 22 executes computer program instructions. In the course of executing these instructions, the processor may issue data and program instruction access commands. Data and program instructions are stored as data in the main memory 26.
The main memory 26 is the memory device which communicates directly with the processor 22. The main memory 26 includes an array of storage locations for storing data. Data is typically organized into lines of data words. A typical data word consists of eight bits (i.e., logical "0s" and "1s"). Each physical storage location, or address, is represented by a number which identifies the storage location in main memory. The system bus 24 transfers data addresses and commands between the devices, i.e., the processor 22, main memory 26, and I/O bridge 28, connected thereto.
A typical computer main memory 26 may be a RAM which stores a number of computer programs and data tables which are currently used by the processor 22. All other information not being currently used by the processor 22 is stored in an auxiliary memory 31, such as a hard disk, and this information is transferred to the main memory 26 on a demand basis.
When several programs reside in the main memory 26, the computer system is in a "multi-programming environment". In a multi-programming environment, computer programs and other data are transferred to and from the auxiliary memory 31 and the main memory 26 as required by the processor 22. In a multi-programming environment, it may be necessary to move programs and data to different locations in the main memory 26. It may also be necessary to separate the programs into parts in order to fit the program into the spaces available in the main memory 26. In addition, in a multi-programming environment sometimes it is desirable to vary the amount of memory used by a particular program; and to prevent a program from changing other programs.
As programs are loaded into a computer's main memory from an auxiliary memory 31, memory size constraints and other factors such as existing memory usage of the main memory 26 require programs to be stored in non-continuous memory areas. Thus, a program which is logically continuous (i.e., flows from one instruction to the next) may be physically stored in memory in a non-continuous way (i.e., one instruction may not be physically located next to the previous or subsequent instruction). Therefore, a computer needs a way to keep track of programs and data stored in the main memory 26. Thus, memory management systems were created to supervise the flow of information throughout the computer and to keep track of and locate each command of a computer program or other data stored in main memory 26.
A typical memory management system comprises both software and hardware for managing various programs stored in a computer's main memory 26. The memory management software portion of the system may be part of an overall operating system available in many computers. A memory management hardware unit is described below.
FIG. 1 shows a memory management unit (MMU) 32 connected to the data bus 24. A typical memory management hardware unit 32 has three basic components. The first component performs dynamic storage relocation which maps logical memory addresses to physical memory addresses. A typical dynamic storage relocation hardware performs a mapping process. Because the program size and the logical structure of the program to be stored in main memory do not always allow a program to be physically stored in continuous memory addresses, it is often convenient to divide the programs and data into logical parts called segments. A segment is a set of logically related instructions or data elements. A segment may be generated by the programmer or by the operating system. An example of a segment is a sub-routine, a data array, a symbol table, or a user's program.
The second component of a typical memory management unit 32 ("MMU") performs a function allowing different users to share common programs stored in memory. Program sharing is important to a multi-programming system. For example, several users may wish to compile programs written in a particular programming language. These users should be able to share a single copy of the compiler program rather than each having to use a separate copy in memory.
The third component of a typical MMU protects information against unauthorized access between users and preventing users from changing operating system functions. Information protection is necessary, for example, to prevent unwanted interaction or one user's unauthorized copying of another user's program. Another aspect of this protection is preventing a user from performing operating system functions or to maintain the secrecy of certain confidential information or programs.
Each program instruction in a program segment may be either a virtual address or a logical address. A virtual address is an address which correlates a data word in a program to its location in physical memory. The physical memory space in the main memory 26 is divided into groups of equal size. The virtual memory groups the computer program into "pages" of the same size as the physical memory groups. A logical address is similar to a virtual address, except that logical address space is associated with variable-length segments rather than fixed-length pages. These variable-length segments, if large, may be sub-divided into smaller fixed length pages.
As seen in FIG. 2, a logical address 33 is partitioned into three fields, a segment field 34, a page field 36, and a word field 38. The segment field specifies 34 a segment number, the page field 36 specifies the page within the segment, and the word field 38 gives the specific word within the page. The length of the segment may vary from one page to as many as 2.sup.k pages, where k is the number of bits in the page field.
FIG. 2 shows how a logical address is mapped into a physical address by a conventional memory management unit. The logical address refers to a particular data word, such as a program instruction (also referred to as a command or task) or piece of data. Although typically this data word logically resides between related instructions or data within a program, it may physically reside at a location remote from logically adjacent instructions or data.
Consider the following example illustrated in FIG. 2. A program having a number of segments is to be loaded into main memory 26. The segment number entered in the segment field 34 of the logical address refers to an address for an entry in a table called a segment table 40. When the program is physically loaded into the main memory 26, the program segments are distributed among the blocks of empty space in physical memory found by the operating system. The correspondence between the physical memory block and logical page number is entered on a segment table 40.
The data word located at logical address 6027E (all numbers are in hexadecimal) is requested by the processor 22. This means that word 7E (i.e., the 126th word) on page 2 of segment 6 is requested.
The entry in the segment table 40 is called a page table base. The page table base corresponding to the logical address segment number is added to the page number given in the logical address (i.e., the entry in the page field 36 of the logical address). The sum of these numbers produces a pointer which points to an address for an entry in a table called a page table 42. In this example, segment 6 has a base address 35. The segment has five pages 35-39. Thus, the page table 42 location for page 2 of segment 6 is at location 35+2=37 on the page table 42.
The value found in the page table provides a "block number". A "block number" is the most significant digits of a physical address in physical memory where the data corresponding to the logical address is located. The "block" typically includes a plurality of physically contiguous data words and thus represents a "block" of physical memory. If a virtual address is used, these "blocks" are the equal sized portions of memory. If a logical address is used, these "blocks" may vary in size. In this example, that block is 019.
The block number in the page table 42 is concatenated with the entry in the word field 38 of the logical address 32 of FIG. 2 in the logical address to produce the final physical mapped address. Block 019 is concatenated with word field entry 7E to provide the 20-bit (in binary) physical address 0197E. This physical address is where the requested data word physically resides in main memory 26. This data word may now be accessed from the main memory 26 and delivered via the data bus 24 to the processor 22.
The segment table 40 and page table 42 may be stored in two separate small memories or in main memory 26. In either case, a memory reference from the processor 22 requires three memory accesses: a first access to obtain the page table base from the segment table 40, a second access to obtain the block number from the page table 42, and a third access to retrieve the requested data word from main memory 26. This slows the system significantly in comparison to a conventional system which directly accesses the main memory and thus, requires only one reference to memory.
The memory shown in FIG. 3 is used to avoid this speed penalty. FIG. 3 shows a fast associative memory 44, which is often used to hold a number of the most recently referenced table entries. When a given block is referenced, the block's value and its corresponding segment and page numbers are entered into the associative memory 44. The mapping process is performed by first comparing the logical address with the entries in the associative memory 44. If the segment and page entries 34, 36 of the logical address 32 match a segment and page stored in the associative memory 44, the block stored in the associative memory 44 is concatenated with the word field entry 38 in the logical address 32 to produce the physical address. The mapping delay is only that of searching the associative memory 44. If no match occurs, the mapping process is performed using the slower mapping table of FIG. 2 and the segment and page number for the requested block is stored in the associative memory 44 for future reference.
FIG. 4A illustrates one type of prior art memory management unit 45 which is disclosed in U.S. Pat. Nos. 4,488,256 and 10 4,473,878 to Zolnowsky et al. These references disclose translating a logical (or virtual) address 33 into a physical address using, for example, a fully associative memory 46. Each entry in the memory is mapped to one page of space. This method uses a mapping table 47 to translate from the logical to the physical address. This memory management unit searches the mapping table 47 to determine the physical page number of the requested data. This method performs a 1-to-1 mapping table search with a "match/no match" result.
FIG. 4B illustrates a second memory management unit 50 which is disclosed in U.S. Pat. Nos. 5,321,836 and 4,972,338 to Crawford et al. and 4,442,484 to Childs, Jr. et al. Segments describe separately protected areas of memory. All of the data words in a segment have the same "protection attribute." These attributes protect the data word from being inadvertently corrupted. These references disclose address translation using segment descriptor tables such as a global descriptor table (GDT) and a local descriptor table (LDT). The logical address base of a data word (or task) includes the descriptors in the GDT and LDT.
This second memory management unit performs a virtual to physical address translation as follows. A virtual address 33 contains a segment field 34 and an offset field 52. The segment field 34 is a "segment selector" and the offset field locates the data word within the segment. The segment field identifies the proper entry on a segment table 40. The segment table 40 entry contains a base address of the segment; the limit (or size) of the segment; and the protection attribute of the segment. The offset 52 is added with the entry of the segment table 40 to obtain a physical address. The offset of the virtual address is compared with the segment limit by a comparator 54. If the offset is outside of the limit, a fault is generated. A second translation which divides the physical address into pages may also be performed.
FIG. 4C provides an example of a drawback of the prior art methods. If a program is to be loaded into main memory 26, and the associative memory is unavailable or turned off (i.e., the segments are not further divided into pages), the program segment allocation is performed by the user or a compiler. In this case, there are three segments having 25k, 20k, and 63k bytes, respectively. Each segment has a different protection attribute. The operating system has to search the main memory 26 for physical memory space and load the segment into these spaces. The physical memory space includes one 24k, two 60k, and one 40k spaces. Even though the physical available space is 24k+60k+60K+40k=184k bytes and the program size is 25k+20k+63k=108k bytes, the 63k byte segment cannot be loaded into the main memory 26 because there is insufficient segment space, even though the amount of physical memory exceeds the amount of program memory by 76k bytes.
It is an object of the present invention to provide an improved apparatus and method for a memory management unit.